#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

#define MAX_TREES 3    // 森林中树的最大数量
#define MAX_NODES 30   // 每棵树的最大结点数
#define MAX_CHILDREN 2 // 每个结点的最大孩子数（二叉树）

// 孩子结点（链表结构）
typedef struct ChildNode
{
    int childIndex;         // 孩子在数组中的下标
    struct ChildNode *next; // 指向下一个孩子的指针
} ChildNode;

// 树结点结构（顺序存储）
typedef struct
{
    int data;              // 结点数据
    ChildNode *firstChild; // 指向第一个孩子的指针
} TreeNode;

// 树结构
typedef struct
{
    TreeNode nodes[MAX_NODES]; // 结点数组
    int rootIndex;             // 根结点索引（-1表示空树）
    int nodeCount;             // 当前结点数
} Tree;

// 森林结构
typedef struct
{
    Tree trees[MAX_TREES]; // 树数组
    int treeCount;         // 当前树的数量
} ChildForest;

// 1. 初始森林
void InitForest(ChildForest &F)
{
    F.treeCount = 0;
    for (int i = 0; i < MAX_TREES; i++)
    {
        F.trees[i].rootIndex = -1;
        F.trees[i].nodeCount = 0;
        // 初始化所有结点
        for (int j = 0; j < MAX_NODES; j++)
        {
            F.trees[i].nodes[j].data = -1; // -1表示无效结点
            F.trees[i].nodes[j].firstChild = NULL;
        }
    }
}

// 2. 销毁森林
void DestroyForest(ChildForest &F)
{
    for (int i = 0; i < F.treeCount; i++)
    {
        // 释放所有孩子链表
        for (int j = 0; j < MAX_NODES; j++)
        {
            ChildNode *p = F.trees[i].nodes[j].firstChild;
            while (p != NULL)
            {
                ChildNode *temp = p;
                p = p->next;
                free(temp);
            }
            F.trees[i].nodes[j].firstChild = NULL;
        }
        // 重置树状态
        F.trees[i].rootIndex = -1;
        F.trees[i].nodeCount = 0;
    }
    F.treeCount = 0;
}

// 3. 插入结点（重点检查部分）
bool InsertNode(Tree &T, int value, int parentIndex, int childPosition)
{
    // 查找可用位置
    int newIndex = -1;
    for (int i = 0; i < MAX_NODES; i++)
    {
        if (T.nodes[i].data == -1)
        {
            newIndex = i;
            break;
        }
    }
    if (newIndex == -1)
    {
        printf("Error: Tree is full\n");
        return false;
    }

    // 设置新结点
    T.nodes[newIndex].data = value;
    T.nodes[newIndex].firstChild = NULL;

    // 处理根结点
    if (parentIndex == -1)
    {
        if (T.rootIndex != -1)
        {
            printf("Error: Root already exists\n");
            T.nodes[newIndex].data = -1;
            return false;
        }
        T.rootIndex = newIndex;
        T.nodeCount++;
        return true;
    }

    // 检查父结点有效性
    if (parentIndex < 0 || parentIndex >= MAX_NODES || T.nodes[parentIndex].data == -1)
    {
        printf("Error: Invalid parent node\n");
        T.nodes[newIndex].data = -1;
        return false;
    }

    // 检查孩子位置有效性
    if (childPosition < 0 || childPosition >= MAX_CHILDREN)
    {
        printf("Error: Invalid child position\n");
        T.nodes[newIndex].data = -1;
        return false;
    }

    // 创建新孩子结点
    ChildNode *newChild = (ChildNode *)malloc(sizeof(ChildNode));
    if (!newChild)
    {
        printf("Error: Memory allocation failed\n");
        T.nodes[newIndex].data = -1;
        return false;
    }
    newChild->childIndex = newIndex;
    newChild->next = NULL;

    // 插入到孩子链表（重点检查部分）
    ChildNode *prev = NULL;
    ChildNode *curr = T.nodes[parentIndex].firstChild;

    // 遍历到指定位置
    for (int i = 0; i < childPosition && curr != NULL; i++)
    {
        prev = curr;
        curr = curr->next;
    }

    // 插入到链表头部
    if (prev == NULL)
    {
        newChild->next = T.nodes[parentIndex].firstChild;
        T.nodes[parentIndex].firstChild = newChild;
    }
    // 插入到链表中间或尾部
    else
    {
        newChild->next = prev->next;
        prev->next = newChild;
    }

    T.nodeCount++;
    return true;
}

// 4.1 前序遍历（递归）
void PreOrder(Tree T, int index)
{
    if (index < 0 || index >= MAX_NODES || T.nodes[index].data == -1)
    {
        return;
    }

    printf("%d ", T.nodes[index].data); // 访问当前结点

    // 遍历所有孩子
    ChildNode *p = T.nodes[index].firstChild;
    while (p != NULL)
    {
        PreOrder(T, p->childIndex);
        p = p->next;
    }
}

// 4.2 后序遍历（递归）
void PostOrder(Tree T, int index)
{
    if (index < 0 || index >= MAX_NODES || T.nodes[index].data == -1)
    {
        return;
    }

    // 先遍历所有孩子
    ChildNode *p = T.nodes[index].firstChild;
    while (p != NULL)
    {
        PostOrder(T, p->childIndex);
        p = p->next;
    }

    printf("%d ", T.nodes[index].data); // 访问当前结点
}

// 4.3 层序遍历（队列实现）
void LevelOrder(Tree T)
{
    if (T.rootIndex == -1)
        return;

    int queue[MAX_NODES];
    int front = 0, rear = 0;

    queue[rear++] = T.rootIndex; // 根结点入队

    while (front < rear)
    {
        int index = queue[front++];
        printf("%d ", T.nodes[index].data); // 访问结点

        // 所有孩子入队
        ChildNode *p = T.nodes[index].firstChild;
        while (p != NULL)
        {
            queue[rear++] = p->childIndex;
            p = p->next;
        }
    }
}

// 4.4 森林遍历
void TraverseForest(ChildForest F, const char *order)
{
    for (int i = 0; i < F.treeCount; i++)
    {
        if (F.trees[i].rootIndex == -1)
            continue;

        printf("Tree %d: ", i + 1);

        if (strcmp(order, "preorder") == 0)
        {
            PreOrder(F.trees[i], F.trees[i].rootIndex);
        }
        else if (strcmp(order, "postorder") == 0)
        {
            PostOrder(F.trees[i], F.trees[i].rootIndex);
        }
        else if (strcmp(order, "levelorder") == 0)
        {
            LevelOrder(F.trees[i]);
        }
        printf("\n");
    }
}

int main()
{
    ChildForest F;
    InitForest(F);

    // 添加三棵树到森林
    F.treeCount = 3;

    // 构建第一棵树 (1为根，2为左孩子，3为右孩子)
    InsertNode(F.trees[0], 1, -1, 0); // 根结点
    InsertNode(F.trees[0], 2, 0, 0);  // 左孩子（位置0）
    InsertNode(F.trees[0], 3, 0, 1);  // 右孩子（位置1）

    // 构建第二棵树 (4为根，5为左孩子，6为右孩子)
    InsertNode(F.trees[1], 4, -1, 0); // 根结点
    InsertNode(F.trees[1], 5, 0, 0);  // 左孩子
    InsertNode(F.trees[1], 6, 0, 1);  // 右孩子

    // 构建第三棵树 (7为根，8为左孩子，9为右孩子)
    InsertNode(F.trees[2], 7, -1, 0); // 根结点
    InsertNode(F.trees[2], 8, 0, 0);  // 左孩子
    InsertNode(F.trees[2], 9, 0, 1);  // 右孩子

    // 遍历测试
    printf("Forest preorder traversal:\n");
    TraverseForest(F, "preorder");

    printf("\nForest postorder traversal:\n");
    TraverseForest(F, "postorder");

    printf("\nForest levelorder traversal:\n");
    TraverseForest(F, "levelorder");

    // 销毁森林
    DestroyForest(F);
    printf("\nForest destroyed\n");

    return 0;
}